# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def getIntersectionNode(self, headA: ListNode, headB: ListNode):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        mid_set = set()
        while headA:
            mid_set.add(headA)
            headA = headA.next
        mid_set.add(None)
        while True:
            if headB in mid_set:
                return headB
            else:
                headB = headB.next
